//
//  Problem303.swift
//  TestProject
//
//  Created by 武侠 on 2021/2/19.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 303. 区域和检索 - 数组不可变
 给定一个整数数组  nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

 实现 NumArray 类：

 NumArray(int[] nums) 使用数组 nums 初始化对象
 int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）
  

 示例：
 输入：
 ["NumArray", "sumRange", "sumRange", "sumRange"]
 [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
 输出：
 [null, 1, -1, -3]

 解释：
 NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
 numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
 numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
 numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
  

 提示：

 0 <= nums.length <= 104
 -105 <= nums[i] <= 105
 0 <= i <= j < nums.length
 最多调用 104 次 sumRange 方法
 */
@objcMembers class Problem303: NSObject {
    func solution() {
        let nums = [-2, 0, 3, -5, 2, -1]
        let obj = NumArray(nums)
        print(obj.sumRange(0, 5))
    }
}

/*
 动态规划
 1: 创建一个数组dp[len]
 2: dp[i]: sum(0...i)的和
 3: sumRange(i, j) = dp[j] - dp[i] + nums[i]
 */
class NumArray {
    var nums:[Int]?
    var dp:[Int]!
    
    init(_ nums: [Int]) {
        if nums.count == 0 {
            return
        }
        
        self.nums = nums
        dp = Array(repeating: 0, count: nums.count)
        dp[0] = nums[0]
        for i in 1..<nums.count {
            dp[i] = dp[i-1] + nums[i]
        }
    }
    
    func sumRange(_ i: Int, _ j: Int) -> Int {
        guard let safeNums = self.nums else {
            return 0
        }
        return dp[j] - dp[i] + safeNums[i]
    }
}
